# -*- coding:utf-8 -*-
class Solution:
    # def InversePairs(self, data):
    #     # write code here
    #     if len(data) <= 0:
    #         return 0
    #     d = []
    #     for i in range(len(data)):
    #         d.append(data[i])
    #     d = sorted(d)
    #     count = 0
    #     i = 0
    #     while len(d) > i:
    #         count += data.index(d[i])
    #         data.remove(d[i])
    #         i += 1
    #     return count % 1000000007

    # def InversePairs(self, data):
    #     length = len(data)
    #     if data == None or length <= 0:
    #         return 0
    #     copy = [0] * length
    #     for i in range(length):
    #         copy[i] = data[i]
    #
    #     count = self.InversePairsCore(data, copy, 0, length - 1)
    #     return count
    # def InversePairsCore(self, data, copy, start, end):
    #     if start == end:
    #         copy[start] = data[start]
    #         return 0
    #     length = (end - start) // 2
    #     left = self.InversePairsCore(copy, data, start, start + length)
    #     right = self.InversePairsCore(copy, data, start + length + 1, end)
    #     i = start + length
    #     j = end
    #     indexCopy = end
    #     count = 0
    #     while i >= start and j >= start + length + 1:
    #         if data[i] > data[j]:
    #             copy[indexCopy] = data[i]
    #             indexCopy -= 1
    #             i -= 1
    #             count += j - start - length
    #         else:
    #             copy[indexCopy] = data[j]
    #             indexCopy -= 1
    #             j -= 1
    #     while i >= start:
    #         copy[indexCopy] = data[i]
    #         indexCopy -= 1
    #         i -= 1
    #     while j >= start + length + 1:
    #         copy[indexCopy] = data[j]
    #         indexCopy -= 1
    #         j -= 1
    #     return left + right + count

    def InversePairs(self, data):
        # write code here
        if len(data) == 0:
            return 0
        return self.mergesort(data, 0, len(data) - 1) % 1000000007
    def mergesort(self, data, s, e):
        if s == e:
            return 0
        mid = (s + e) >> 1
        a =  self.mergesort(data, s, mid) + self.mergesort(data, mid + 1, e) +self.merge(data, s, e, mid)
        return a
    def merge(self, data, s, e, r):
        h = []
        p1 = s
        p2 = r + 1
        res = 0
        while p1 <= r and p2 <= e:
            if data[p1] > data[p2]:
                res += r - p1 + 1
                h.append(data[p2])
                p2 += 1
            else:
                h.append(data[p1])
                p1 += 1
        while p1 <= r:
            h.append(data[p1])
            p1 += 1
        while p2 <= e:
            h.append(data[p2])
            p2 += 1
        for i in range(len(h)):
            data[s+i] = h[i]
        return res


a = [1,3,2,0]
s=Solution()
m = s.InversePairs(a)
print(m)